module fn.adt.tree.Transform

open fn.adt.Tree


type TreeOp<'D> =
    | Nop
    | Root of 'D
    | Subtree of Tree<'D>

type TreeTransform<'D> (xformer: Tree<'D> -> Tree<'D> option) =
    class
        let _xformer = xformer
        
        member this.apply tree =
            match _xformer tree with
            | Some t -> t
            | None ->
                match tree with
                | Node(r, sb) -> Node(r, [for s in sb -> this.apply s])
        
        static member inline ( =~ ) (this: TreeTransform<'D>,tree: Tree<'D>) =
            this.apply tree
    end

type MappingTreeTransform<'S,'T> (xformer : Tree<'S> -> TreeOp<'T>) =

    member this.apply (Node(r, sb) as tree) =
        match xformer tree with
        | Root r' ->
            Node(r', [for s in sb -> this.apply s])
        | Subtree t' -> t'
        | Nop -> 
            match r :> obj with
            | :? 'T as t -> Node(t, [for s in sb -> this.apply s])
            | _ -> failwith (sprintf "incompatible types: '%O' and '%O'" typeof<'S> typeof<'T>)

    static member inline ( =~ ) (this: MappingTreeTransform<'S,'T>, tree) =
        this.apply tree
